Daily notes from LeetCode practice and algorithm study
(node, stops_used). Do this right after #743 to see concretely why Dijkstra fails here.
Given a "-"-separated string of tokens, build a frequency map of how often token Y follows token X. Then, given the map, a seed token, and an output length, walk the chain: convert each token's next-token frequencies into probability intervals, draw random.random(), and find which interval it lands in.
def get_next_token_given_intervals(seed, token_probabilities): probability = random.random() for token, (start, end) in token_probabilities[seed]: if start <= probability < end: return token # falls through here more often than it should — see note
EXIT_PAGE) that never appears as a key in the frequency map, only as someone else's next-token. token_probabilities[seed] for it is an empty list, so the for loop never runs and falls straight to the fallback branch, every time, not rarely. Told the interviewer: on a dead end, end the output early rather than pad or error.def build_retool_app(frequency_map, seed, length): token_probabilities = transform_frequency_dict_to_probabilities(frequency_map) output_tokens = [seed] current_token = seed for _ in range(length): if not token_probabilities.get(current_token): break # dead end (e.g. EXIT_PAGE) — stop early current_token = get_next_token_given_intervals(current_token, token_probabilities) output_tokens.append(current_token) return '-'.join(output_tokens)
1.0 (cumulative += rounding), but the odds of random.random() landing in it are ~1 in 2⁵³ (~1.1e-16) — essentially never in practice. If the fallback branch fires reliably, look for a dead end like this one first, not float precision.A defaultdict factory just needs to be a zero-arg callable. A class with a no-arg __init__ qualifies directly, same as list/int. A lambda is only needed when the value itself needs to be built by calling something at access time, e.g. another defaultdict.
# Custom class as the value type — no lambda needed class Node: def __init__(self): self.children = defaultdict(Node) # char -> Node self.is_end = False # Nested defaultdict — DOES need a lambda groups = defaultdict(lambda: defaultdict(list)) groups['a']['b'].append(1)
defaultdict(defaultdict(list)) fails immediately, defaultdict(list) evaluates right away to one built instance, and a dict instance isn't callable, so the outer defaultdict has no valid factory. The lambda defers construction so a fresh defaultdict(list) gets built per new outer key.is_end — a node can be a word AND a prefixInserting "apple" then "apple tree" shares the path a→p→p→l→e, then continues from that same e node with " tree". That e node ends up with is_end = True (since "apple" is a complete word) and a child continuing toward "apple tree" at the same time.
is_end has to be its own independent flag per node, not derived from leaf-ness.ord() — character → code pointord(c) returns a character's integer Unicode code point. ord('a') == 97, ord('z') == 122, ord('A') == 65.
ord(c) - ord('a') # maps 'a'->0, 'b'->1, ..., 'z'->25
insert/search/startsWith, each node holding a dict of char → Node plus an is_end flag.
class Node: def __init__(self, val): self.is_end = False self.val = val self.children = {} class Trie: def __init__(self): self.root = Node("") def insert(self, word: str) -> None: node = self.root for c in word: if c not in node.children: node.children[c] = Node(c) node = node.children[c] node.is_end = True def search(self, word: str) -> bool: node = self.root for c in word: if c not in node.children: return False node = node.children[c] return node.is_end def startsWith(self, prefix: str) -> bool: node = self.root for c in prefix: if c not in node.children: return False node = node.children[c] return True
children: a dict is correct and general (any character set, only stores children that exist). For this problem specifically (lowercase a-z only), the classic optimized alternative is children = [None] * 26 indexed by ord(c) - ord('a') — faster (array index, no hashing) and more cache-friendly, at the cost of being locked to a fixed alphabet and wasting slots when branching is sparse.dict, not defaultdict(Node), for children: search/startsWith need to distinguish "child missing → return False" from "auto-create." A defaultdict would silently create an empty Node on a failed lookup inside search, corrupting the trie instead of signaling absence. Plain dict + explicit if c not in node.children avoids that trap.Backtracking DFS from every cell matching word[0], using the get_neighbors helper from the cheatsheet plus a temporary "#" marker on board[i][j] to block revisiting during the current path, restored on the way back out regardless of outcome.
backtrack(n_i, n_j, starting_index + 1) without capturing its return value, so a successful deep match never made it back up the call stack, every frame fell through to its own return False. Fix: if backtrack(...): return True at every call site, so success short-circuits immediately through every enclosing frame.Trie + grid backtracking, the boss version of #79 and #208 combined. Hinges on three things:
word is None and it has no children left, nothing further can ever be found through it — delete it from the parent's array. No parent pointer needed, the caller already holds the parent node and index from making the call.backtrack only needs (i, j, node) — position on the board plus position in the trie, nothing else to thread through.# Pruning — after recursing into a child, check if it's now dead child = node.children[char_index] if child: ... backtrack(n_i, n_j, child) if child.word is None and all(c is None for c in child.children): node.children[char_index] = None # dead branch, prune # Must skip '#' before translating to an index — '#' isn't a-z, # so ord('#') - ord('a') is negative and indexes out of range if board[n_i][n_j] == '#': continue
trie.root.children, not just inside backtrack — otherwise the root level never gets cleaned up and later starting cells keep re-entering exhausted branches.Given a flaky run_job (fails ~70% of the time) wrapped in a 3-retry process_with_retries, the ask was really "how do you unit test this deterministically." Answer: don't hardcode the call, inject the runner as a parameter defaulting to the real one, so tests can pass a fake with controlled failure counts.
def process_with_retries(job_id, runner=run_job): last_error = None for attempt in range(3): try: return runner(job_id) except NetworkError as error: last_error = error raise Exception(f"Failed after 3 tries: {last_error}")
catch isn't Python (except), and if i == 3 never fires against range(3) (0,1,2 only) — an off-by-one that silently swallows the final failure.Before reaching for a prefix/suffix array, ask whether you need a fixed aggregate (sum, min, max) or whether you need to recall a specific past value. A fixed aggregate only needs one running number carried forward — that's Pivot Index and Trapping Rain Water below. Subarray Sum Equals K is the counter-example: it asks "did this exact prefix value occur before," which a single running total can't answer, so it genuinely needs the hashmap. Logged as a new panel in leetcode_cheatsheet.html.
First pass used two full prefix/suffix arrays, O(n) space, correct but more than needed. Optimized to O(1) space: one pass for total, then a running left_sum where right_sum = total - left_sum - num is derived, not stored.
total = sum(nums) left_sum = 0 for i, num in enumerate(nums): right_sum = total - left_sum - num if left_sum == right_sum: return i left_sum += num return -1
Same space upgrade as Pivot Index: went from O(n) maxLeft/maxRight arrays to O(1) two-pointer. Wrote two valid orderings — update-max-then-add-water (the "new record" case self-corrects to zero water, no guard needed) vs. add-water-then-update-max (needs an explicit max(0, ...) guard, but matches the mental model more directly). Landed on the second as clearer.
left, right = 0, len(height) - 1 maxLeft = maxRight = water = 0 while left < right: if height[left] <= height[right]: water += max(0, maxLeft - height[left]) maxLeft = max(maxLeft, height[left]) left += 1 else: water += max(0, maxRight - height[right]) maxRight = max(maxRight, height[right]) right -= 1 return water
height[left] <= height[right], some wall to the right (at minimum height[right] itself) is already ≥ height[left], so the right side can never be the bottleneck for position left — maxLeft alone decides it, no need to know the true maxRight.min(maxLeft, maxRight), independent of the cell's own height. The cell's height only decides whether it pokes above that surface (zero water) or sits below it — which is why most cells (local peaks, monotonic slopes) produce nothing.Hash map plus a doubly linked list, both operations O(1). The dict maps key → node. The list orders nodes by recency: front (behind a dummy head) is least recently used, back (before a dummy tail) is most recently used. Any use — get or put — unlinks the node and re-adds it at the back. Eviction removes the node right after the dummy head. Solved it myself from Socratic hints.
# Node: key, value, prev, next # dict key_to_node; dummy_head <-> dummy_tail sentinels _remove(node): # splice out node.prev.next = node.next node.next.prev = node.prev _add_to_tail(node): # relink existing node, no alloc link (dummy_tail.prev) <-> node <-> dummy_tail get(key): if key missing: return -1 node = key_to_node[key] _remove(node); _add_to_tail(node) # reuse node, dict untouched return node.value put(key, value): if key present: node = key_to_node[key]; _remove(node) node.value = value; _add_to_tail(node); return if full: lru = dummy_head.next _remove(lru); del key_to_node[lru.key] # del before losing ref node = Node(key, value); _add_to_tail(node); key_to_node[key] = node
Node on every get / put-existing instead of reusing the one I already held. Fix: unlink and relink the same object (set .value in the put case). On a get the dict entry never changes.key in the node (needed to del the dict entry on eviction), and delete from the dict before dropping the evicted node's reference.prev and next. No empty-list or first/last-node special cases — _remove and _add_to_tail stay branchless.Given {"C": .5, "D": .5}, output an experience so that over many calls the split matches the given probabilities, but any single call has to be reproducible, not truly random. The hash function itself was given, not something I had to implement — my job was the bucketing logic around it. The trick is to replace random() with the provided stable hash: hash a key into a large integer, normalize it into [0, 1), then walk the cumulative probabilities (0-.5 → C, .5-1 → D) to find which bucket the normalized value falls into.
# hash_fn(key) -> stable int, provided by the interviewer def bucket(key: str, weights: dict) -> str: h = hash_fn(key) frac = (h % 10_000) / 10_000 # normalize to [0, 1) cumulative = 0 for name, weight in weights.items(): cumulative += weight if frac < cumulative: return name return list(weights)[-1] # float-rounding fallback
hash() would not work) makes the bucket a pure function of the key — no storage needed, and it's automatically consistent across servers/restarts as long as everyone hashes the same key.user_id alone → same user always gets the same experience for a given feature, on every call.user_id + feature_name together → a user's bucket in one feature doesn't determine their bucket in another. Without this, whichever bucket a user lands in on the first hash would silently correlate across every feature that reuses it (e.g. always landing in the "control" side of every A/B test).Greedy, sort by end time ascending. Keep an interval if its start is ≥ the previous kept interval's end; the answer is n - count_kept. Sorting by end (not start) is the key choice: always keeping the interval that frees up time earliest leaves the most room for everything after it.
def eraseOverlapIntervals(intervals): sorted_intervals = sorted(intervals, key=lambda x: x[1]) count = 0 prev_end = float('-inf') for cur_start, cur_end in sorted_intervals: if cur_start >= prev_end: count += 1 prev_end = cur_end return len(intervals) - count
float(-inf) evaluates the bare name inf first, which isn't defined unless you separately imported it — that line throws NameError on its own. You want the string form, float('-inf'), or import math; math.inf. Same trap as float(-infinity) — inf is only special inside a string literal passed to float().Two approaches, both O(n log n) from sorting, O(n) space.
Min-heap (end times): sort by start, push each end time onto a min-heap; before pushing, pop off any room whose end time is ≤ the current start (that room is free again). The heap size at any point is the number of rooms in use, so the max size seen is the answer. Worth reaching for when you need more than just the count — e.g. which physical room a meeting was assigned to.
sorted_intervals = sorted(intervals, key=lambda x: x[0]) end_time_heap = [] max_rooms = 0 for start, end in sorted_intervals: while end_time_heap and start >= end_time_heap[0]: heapq.heappop(end_time_heap) heapq.heappush(end_time_heap, end) max_rooms = max(max_rooms, len(end_time_heap)) return max_rooms
Sweep line (cleaner when you only need the count): turn every interval into a +1 event at its start and a -1 event at its end, sort all events by time, and run a prefix sum, tracking the max.
events = [] for start, end in intervals: events.append((start, 1)) events.append((end, -1)) sorted_events = sorted(events, key=lambda x: (x[0], x[1])) max_count = 0 current_count = 0 for time, delta in sorted_events: current_count += delta max_count = max(max_count, current_count) return max_count
(x[0], x[1]) matters: when a meeting ends exactly when another starts, the -1 end event must be processed before the +1 start event at the same timestamp, otherwise you'd double-count a room that's actually free. Sorting by (time, delta) puts -1 before +1 automatically since -1 < 1 — no extra tiebreak logic needed.Sort by start, then one pass: for each interval, either extend the last merged interval (if it overlaps) or append a new one. The "sort by start" key is what makes the single sweep correct.
sorted_intervals = sorted(intervals, key=lambda x: x[0]) merged = [] for start, end in sorted_intervals: last_end = None if len(merged) == 0 else merged[-1][1] if last_end is not None and start <= last_end: # overlaps merged[-1][1] = max(last_end, end) else: merged.append([start, end]) return merged
Three regions, one linear pass (input is sorted): intervals entirely before the new one, intervals that overlap it, and intervals entirely after. Emit the first group as-is, collapse the overlapping group into one merged interval, then emit the rest. output starts empty; new_start, new_end come from newInterval.
# phase 1: intervals strictly before the new one while runner < n and intervals[runner][1] < new_start: output.append(intervals[runner]); runner += 1 # phase 2: merge everything that overlaps while runner < n and intervals[runner][0] <= new_end: new_start = min(new_start, intervals[runner][0]) new_end = max(new_end, intervals[runner][1]) runner += 1 output.append([new_start, new_end]) return output + intervals[runner:]
< (cur_end < new_start) so an interval ending exactly at the new start is not "before" — it touches, so it falls into phase 2. Phase 2 uses <= (cur_start <= new_end) so touching counts as overlap. Strict before, inclusive overlap. In the interview, state the touching assumption out loud and give complexity unprompted: O(n) time, O(n) space.Max-heap of remaining counts (negate for Python's min-heap) plus a cooldown queue. Each tick: run the most frequent ready task and bench it with its ready-time, then release anything whose cooldown has elapsed back into the heap. Task names don't matter once benched, so the heap holds counts only.
from collections import Counter, deque freq = Counter(tasks) max_heap = [-count for count in freq.values()] # counts only heapq.heapify(max_heap) cooldown_queue = deque() # (ready_time, remaining_count) cpu_time = 0 while max_heap or cooldown_queue: if max_heap: # else this tick is idle count = heapq.heappop(max_heap) + 1 # use one (toward 0) if count < 0: cooldown_queue.append((cpu_time + n, count)) # bench until cpu_time+n # release cooled-down tasks back into the heap while cooldown_queue and cpu_time >= cooldown_queue[0][0]: heapq.heappush(max_heap, cooldown_queue.popleft()[1]) cpu_time += 1 return cpu_time
maxFreq = highest count, k = how many tie at it. Answer = max(len(tasks), (maxFreq - 1) * (n + 1) + k). The max(len(tasks), …) is the gotcha — with many distinct tasks the gaps fill and there's zero idle. Reach for this when n is huge (a billion idle slots kills the simulation). Retry in ~1 week: derive the formula from the fencepost picture.key=lambda x: x[0]To sort by a specific field, pass a key function that returns the value to sort on. lambda x: x[0] sorts a list of intervals by their start. For a secondary tiebreak, return a tuple: key=lambda x: (x[0], x[1]). sorted() returns a new list; .sort() mutates in place.
is not None, not not xI first wrote if not last_end to mean "there's no previous interval." Bug: a legitimate last_end == 0 is falsy in Python, so not last_end is True and the code wrongly treats a real interval ending at 0 as "no interval." The fix is if last_end is not None, which tests presence, not truthiness.
0, 0.0, "", [], and False are all falsy. Any of them as a valid value breaks a not x presence check.0 or empty and you only want to check "is it set," use is None / is not None. Reserve not x for when you actually mean "empty or zero."Modified binary search. At every step, at least one half around mid is sorted. Check whether target falls inside the sorted half's bounds — if yes, search there; if not, search the other (rotated) half. This stays O(log n) single-path binary search.
while low <= high: mid = (low + high) // 2 if nums[mid] == target: return mid isLeftRotated = nums[low] > nums[mid] isRightRotated = nums[mid] > nums[high] # left half sorted and holds target if not isLeftRotated and nums[low] <= target < nums[mid]: high = mid - 1 # right half sorted and holds target elif not isRightRotated and nums[mid] < target <= nums[high]: low = mid + 1 # otherwise go to whichever half holds the rotation elif isRightRotated: low = mid + 1 else: high = mid - 1 return -1
Binary search for the rotation point. The nums[low] <= nums[high] check does double duty: it's the base case AND a shortcut — if the current segment is already sorted, its first element is the minimum, so return it immediately.
Mid-bias applied correctly (July 5 rule): the keep-mid branch is high = mid, so mid must round down — which (low + high) // 2 does. No infinite loop: the only stall case is mid == high, which needs low == high, and the sorted-check returns before mid is ever computed in that state.
while low <= high: if nums[low] <= nums[high]: # segment sorted -> first is min return nums[low] mid = (low + high) // 2 if nums[low] <= nums[mid]: # left half sorted, drop is on right low = mid + 1 # mid can't be the min, exclude it else: # drop is in left half, mid might be min high = mid # keep mid
We're using Python, so mid is just (low + high) // 2. Integer division rounds down, and Python ints don't overflow, so there's nothing else to memorize.
low = 0, high = 1, round-down mid gives mid = 0 = low. If a branch does low = mid (keeps mid in the window), low never moves and the loop freezes.high = mid. Match rounding to your update. If any branch does low = mid, round up: mid = low + (high - low + 1) / 2. If any branch does high = mid, round down. Mismatch causes the freeze.Exact match: looking for a specific value, return the instant nums[mid] == target. Because you return on hit, mid is never kept in the window — every other branch does mid + 1 or mid - 1, so it always shrinks. Round-down mid is safe, no bias worries. Use while low <= high.
while low <= high: mid = low + (high - low) // 2 if nums[mid] == target: return mid elif nums[mid] < target: low = mid + 1 else: high = mid - 1 return -1 # not found
Boundary search: find the first/last position satisfying a condition ("first element ≥ target", "smallest x where condition is true"). You can't return early because mid might be the answer, so you keep it with low = mid — and now rounding direction matters. This is the core pattern for binary-search-on-answer problems, which Waymo-style questions lean on.
Finds shortest paths from a source node in a weighted graph with non-negative edges. Push (distance, node) tuples onto a min-heap.
prev dict updated on every edge relaxation, then walk backward from target to source. For distance-only problems a dist[] array is enough.if cur_dist > dist[cur_node]: continue): skips outdated heap entries. Without it you'd re-expand neighbors with a worse distance — wasted work but not wrong, since the downstream if new_dist < dist[neighbor] guard prevents bad overwrites.def dijkstra(graph, start): dist = {node: float('inf') for node in graph} dist[start] = 0 heap = [(0, start)] while heap: cur_dist, cur_node = heapq.heappop(heap) if cur_dist > dist[cur_node]: continue for neighbor, weight in graph[cur_node]: new_dist = cur_dist + weight if new_dist < dist[neighbor]: dist[neighbor] = new_dist heapq.heappush(heap, (new_dist, neighbor)) return dist
Python's heapq module is a min-heap only. For a max-heap, negate values on push and un-negate on pop. Push tuples to sort by multiple keys — heapq compares element by element, so (priority, value) naturally sorts by priority first. If two tuples tie and the second element is non-comparable (e.g. a custom object), add a counter as a tiebreaker.
import heapq # Min-heap heap = [] heapq.heappush(heap, 5) smallest = heapq.heappop(heap) # 5 # Max-heap: negate values max_heap = [] heapq.heappush(max_heap, -5) largest = -heapq.heappop(max_heap) # 5 # Tuple unpacking (no parens needed on left side) cur_dist, cur_node = heapq.heappop(min_heap)
Three approaches. The heap approach (push all unique elements negated onto a max-heap, pop k times) is O(n log n) — not O(n log k), because the heap holds all unique elements, not just k. The sort approach has the same complexity. The optimal approach is bucket sort: since frequency is bounded by len(nums), bucket elements by frequency and walk buckets from highest to lowest, stopping at k. O(n) throughout.
# Bucket sort — O(n) buckets = [[] for _ in range(len(nums) + 1)] for num, count in freq.items(): buckets[count].append(num) result = [] for count in range(len(buckets) - 1, 0, -1): for num in buckets[count]: result.append(num) if len(result) == k: return result
Canonical Dijkstra. Find the minimum time for a signal to reach all nodes from source k — equivalent to finding shortest distances from k to every node, then returning the max. If any node is unreachable, return -1.
return -1 if max_distance == float('inf') else max_distance — C-style cond ? a : b doesn't exist in Python.Dijkstra variant — maximize probability instead of minimizing distance. Use a max-heap (negate probabilities). Multiply edge weights instead of adding. The early-exit on end_node is valid for the same reason as standard Dijkstra: probabilities only shrink as more edges are multiplied (each prob ≤ 1), so the first pop of the target is guaranteed maximal.
Sliding window. Expand right unconditionally, shrink left while the window is valid. Track character frequencies for both s and t. Update the shortest window inside the shrink loop.
Approach 1 — Simple (easier to understand): check validity with all(s_freq[c] >= t_freq[c] for c in t_freq) — O(|t|) per iteration.
t_freq = defaultdict(int) s_freq = defaultdict(int) for c in t: t_freq[c] += 1 shortest = "" left = 0 for right in range(len(s)): s_freq[s[right]] += 1 while all(s_freq[c] >= t_freq[c] for c in t_freq): valid_substring = s[left:right+1] if not shortest or len(shortest) > len(valid_substring): shortest = valid_substring s_freq[s[left]] -= 1 left += 1
Approach 2 — Optimized with have / need: instead of checking all characters each iteration, track how many distinct characters have met their frequency threshold. Validity becomes O(1).
need = len(t_freq). Increment have when s_freq[c] reaches t_freq[c] after adding. Decrement have when s_freq[c] drops below t_freq[c] after removing.
need = len(t_freq) have = 0 left = 0 shortest = "" for right in range(len(s)): added_char = s[right] s_freq[added_char] += 1 if s_freq[added_char] == t_freq[added_char]: have += 1 while have == need: valid_substring = s[left:right+1] if not shortest or len(shortest) > len(valid_substring): shortest = valid_substring removed_char = s[left] left += 1 s_freq[removed_char] -= 1 if s_freq[removed_char] < t_freq[removed_char]: have -= 1
Sliding window. A window is valid if window_size - max_freq <= k, where max_freq is the count of the most frequent character inside the window. Expand right every iteration, shrink left until the window is valid again.
Use a for loop on the right pointer, not a while loop with manual initialization. Right expands by one each iteration unconditionally — no pre-seeding or off-by-one handling needed.
left = 0 freq = defaultdict(int) longest = 0 for right in range(len(s)): freq[s[right]] += 1 while (right - left + 1) - max(freq.values()) > k: freq[s[left]] -= 1 left += 1 longest = max(longest, right - left + 1)
Sliding window with a hashmap tracking the last seen index of each character. Instead of maintaining an explicit left pointer, track cur_length directly.
char_to_last_seen = {}
longest = 0
# current sliding window length
window_length = 0
for i, c in enumerate(s):
if c not in char_to_last_seen:
window_length += 1
else:
last_index = char_to_last_seen[c]
# cap at window_length + 1 in case the duplicate is outside the current window
window_length = min(i - last_index, window_length + 1)
char_to_last_seen[c] = i
longest = max(longest, window_length)Crux: min(i - last_seen_idx, cur_length + 1): when a duplicate is found, the new window can extend at most to just past the last occurrence (i - last_seen_idx). But if that duplicate is outside the current window, we shouldn't arbitrarily expand — cap at cur_length + 1, which is what you'd get if the character were new.
Use a stack where each entry tracks the repeat count and accumulated string for the current nesting level. On [, push a new entry. On ], pop and append the repeated string onto the level below. Initialize with [1, ""] as a base so the outermost string needs no special-casing.
Use a list, not a tuple: storing each entry as [count, string] lets you modify the string in place with stack[-1][1] += c. Tuples are immutable, so you'd have to pop and re-push just to append a character — awkward and easy to flag in an interview.
Multi-digit numbers: accumulate digits with digit = 10 * digit + int(c) and reset to 0 on [.
Approach 1 — Interleaving (O(1) space): weave copies between originals (A → A' → B → B'), set random pointers using node.random.next to reach the copy, then extract the copy list in a third pass. The original list is destroyed in the process.
Approach 2 — Hashmap (O(n) space): map each original node to its copy in one pass, then wire up next and random in a second pass using the map. Cleaner and easier to reason about — looking up the copy of any node is O(1).
Monotonic decreasing stack. For each day, pop any previous days that are cooler than the current temperature — those days have found their answer. The days waiting on the stack are always in decreasing temperature order.
Python has no peek() — use stack[-1] to look at the top of the stack without popping.
You can store just the index on the stack and look up the temperature via temperatures[i], but storing (temp, index) pairs is more readable.
A subarray sum equals prefix_sum[j] - prefix_sum[i]. The brute force checks all pairs — O(n²). The insight: for each position j, you already know exactly what earlier prefix sum you need: prefix[j] - k. If you've seen that value before, every occurrence is a valid subarray.
Running hashmap (like Two Sum): instead of storing the full prefix sum array, maintain a single running sum and a map from prefix sum value to how many times it's appeared. No indices needed — just counts. Add prefix_sum_count[0] = 1 before the loop to handle subarrays starting at index 0.
Target = current prefix sum − k, not k − prefix sum.
Two pointers: advance fast by n steps first, then move both until fast.next is None. At that point slow is just before the node to remove, so slow.next = slow.next.next.
Edge case — removing the head: if fast is None after the initial loop, n equals the list length, meaning the head itself needs to be removed. Return head.next early. This also guarantees that by the time you reach slow.next = slow.next.next, slow.next is always a real node — never None.
Use two pointers starting at head — slow moves 1 step, fast moves 2. If there's a cycle they're guaranteed to meet. Move before checking (not after) to avoid a false match at the start.
Why they always meet (never skip): each iteration, slow moves +1 and fast moves +2, so the gap between them shrinks by exactly 1. Starting at gap N, after N steps the gap is 0. It can never jump from 2 to 0 and skip over — it decrements by 1 at a time, so they're guaranteed to land on the same node.
Use a dummy head node so the merged list always has a stable starting point, avoiding special-casing the first node. Walk both lists with a pointer, always attaching the smaller current node and advancing that list's pointer. Once one list runs out, attach the remainder of the other list directly (no need to copy node by node).
Relink, don't copy: attach the existing nodes (cur.next = list1) instead of creating new ListNode copies. Same logic, but O(1) extra space instead of O(n).
def mergeTwoLists(list1, list2): dummy_head = ListNode(0) cur = dummy_head while list1 and list2: if list1.val < list2.val: cur.next = list1 list1 = list1.next else: cur.next = list2 list2 = list2.next cur = cur.next if list1: cur.next = list1 if list2: cur.next = list2 return dummy_head.next
Iteratively walk the list, flipping each node's next pointer to point backward. Before overwriting cur.next, save a reference to the next node so you don't lose the rest of the list. Track prev as the new tail of the reversed portion, and at the end prev is the new head. O(n) time, O(1) extra space.
def reverseList(head): prev = None cur = head while cur: next_node = cur.next cur.next = prev prev = cur cur = next_node return prev
Sort the array, then for each fixed first element use two pointers from both ends to find pairs summing to the target. O(N^2) time, O(1) extra space (besides the sort).
Skipping duplicates: the "no duplicate triplets" rule means the duplicate-skip logic only matters after a valid triplet is found. If two_sum != target, nothing was added to the output, so there's nothing to dedupe — just move the pointer and keep searching. Only when two_sum == target do you need to advance past any repeated values for both left and right (and skip duplicates of the outer loop's fixed element too).
Two pointers starting at both ends, tracking max area as (right - left) * min(height[left], height[right]). Always move the pointer at the shorter height inward.
Why moving the shorter side is correct: moving the taller pointer can never increase the area, since the width shrinks and the limiting height (the shorter side) stays the same or gets worse. Only moving the shorter pointer has a chance of finding a taller wall that could outweigh the lost width.
O(1) extra space version: one pass left-to-right tracks a running prefix_product and writes it into output[i] before updating it. A second pass right-to-left tracks a running suffix_product and multiplies it into output[i]. No separate prefix/suffix arrays needed.
Naming tip — name by role, not type: prefix_product / suffix_product describe what the running value represents in the algorithm, versus generic names like products / rev_products which only describe the data type (an array) and force the reader to infer the role.
String manipulation basics:
''.join(c for c in s.lower() if c.isalnum()) — a generator expression filters and lowercases each char, and .join() collects the results back into a single string..isalnum() checks if a character is a letter or digit, used here to strip out spaces and punctuation during normalization.s[i]), which makes the two-pointer comparison straightforward.Two pointers from both ends, moving inward based on whether the sum is too small or too large. If the true answer is at indices i < j, the pointers can never cross past them: if left already equals i and the sum is still too small, then numbers[right] must already be ≥ numbers[j] (sorted array), forcing the sum ≥ target, a contradiction. So the window only shrinks toward (i, j), never past it, and this only works because the array is sorted.
Return None to signal "not found", or the node itself to signal "found something". Early exit when the current node is p or q — safe because the problem guarantees both exist. If both sides return non-None, this node is the LCA. Otherwise bubble up whichever side found something.
def dfs(node): if not node: return None if node == p or node == q: return node left = dfs(node.left) right = dfs(node.right) if left and right: return node # p and q on opposite sides return left or right # bubble up whichever side found something
The key insight: don't bubble information up — pass constraints down. Every node has a valid range determined by all its ancestors, not just its immediate parent. Pass an upper and lower bound through the recursion so each node knows exactly what range it must fall in.
Going left: current node's value becomes the new upper bound. Going right: current node's value becomes the new lower bound. Initialize with float('inf') and float('-inf') — prefer these over sys.maxsize, which is a real finite integer and would incorrectly reject a BST node whose value equals it.
def dfs(node, max_value, min_value): if not node: return True if node.val >= max_value or node.val <= min_value: return False return dfs(node.left, node.val, min_value) and dfs(node.right, max_value, node.val) return dfs(root, float('inf'), float('-inf'))
Build a reverse graph so that when you decrement in-degrees you get O(1) lookups on neighbors. The in-degree count tells you which nodes are ready to process: when a node's in-degree hits 0, it enters the queue. If any edges remain after processing, the graph has a cycle.
L ← empty list for sorted output S ← all nodes with in-degree == 0 while S is not empty: n = remove(S) append(L, n) for each node m where edge (n → m) exists: remove edge (n → m) if in_degree[m] == 0: insert(S, m) if graph still has edges: return ERROR # cycle detected else: return L # valid topological order
DFS uses the call stack (recursion) — you always have a reference to your ancestors in the current path. This makes it natural for detecting back-edges (cycles) via ancestry tracking.
# DFS — uses recursion / call stack def dfs(node, graph, visited): visited.add(node) for neighbor in graph[node]: if neighbor not in visited: dfs(neighbor, graph, visited) # ancestor path lives in call stack
BFS is level-by-level using an explicit queue — no call stack, no ancestry reference. Kahn's is BFS-based: it doesn't track ancestry; instead it relies on in-degree counts to know when a node is "ready."
# BFS — uses an explicit queue, processes level by level from collections import deque def bfs(start, graph): queue = deque([start]) visited = {start} while queue: node = queue.popleft() for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) # no stack, no ancestry
defaultdict
Used heavily today for building adjacency lists and in-degree maps. defaultdict(list)
avoids needing to check if a key exists before appending — cleaner graph construction in problems like Course Schedule.
Hash map where the key is a sorted tuple of characters (or a character-count tuple). All words that are anagrams of each other map to the same key.
from collections import defaultdict class Solution: def groupAnagrams(self, strs): groups = defaultdict(list) for word in strs: freq = defaultdict(int) for c in word: freq[c] += 1 key = tuple(sorted(freq.items(), key=lambda x: x[0])) groups[key].append(word) return list(groups.values())
Why tuple(): dict keys must be hashable, and a dict (or list) itself is mutable and unhashable. sorted(freq.items()) produces a list of (char, count) pairs in a canonical order, but it's still a list. Wrapping it in tuple() converts it to an immutable, hashable sequence, so it can be used as the key in groups. The sorting step is what makes anagrams (which have the same character counts in some order) map to the same key.
Classic Kahn's application. Build a graph of prerequisites, compute in-degrees, BFS from all nodes with in-degree 0. If you process all courses, no cycle exists.
Snapshot len(queue) at the start of each BFS iteration — that count is exactly how many nodes are on the current level. Process only that many nodes before appending the level's result, so children queued during the loop don't bleed into the current level.
for _ in range(len(queue)): # snapshot: nodes at this level node = queue.popleft() # children appended here are counted in the NEXT iteration
Use len(queue) to snapshot the current level size and a levelSeen bool to ensure only the first node processed per level gets added to the result. Enqueue node.right before node.left so the rightmost node is always dequeued first.
Iterate the grid; when you hit a '1', increment the island count and BFS to sink all connected land cells (mark as '0'). Use a queue to explore all 4 neighbors level by level — avoids DFS recursion which can overflow the call stack on large grids.